import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//leetcode_78:子集
//给你一个整数数组nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
//        解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
//        示例 1：
//        输入：nums = [1,2,3]
//        输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
//        示例 2：
//        输入：nums = [0]
//        输出：[[],[0]]
public class leetcode_78 {

    //回溯算法
    public static List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();//使用Deque主要是考虑可以从末尾删除元素
        //也可以使用List，但是重置状态的时候要计算末尾
        dfs(list,nums,len,path,0);
        return list;
    }

    private static  void dfs(List<List<Integer>> list,int[] nums,int len,Deque<Integer> path,int begin){
        list.add(new ArrayList<>(path));    //一运行就添加一次，因为给的答案里面都有一个空值，
        if(len==begin)//这个是终止条件，因为从题目观察出终止条件是当遍历到最后一个元素的时候就结束
            //所以当数组的长度等于我们遍历到的最后一个元素的位置的时候就可以停止了
            return;

        for(int i = begin;i<len;i++){
            path.add(nums[i]);
            dfs(list,nums,len,path,i+1);//i+1 就是begin
            path.removeLast();//使用ArrayDeque的removeLast()方法删除最后一个元素，也就是重置状态
        }
    }

}
